﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace sf_study
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
        }
    }


    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

    //求 二叉树的深度
    public class Solution
    {
        //递归题解

        // public int MaxDepth(TreeNode root)
        // {
        //     if (root == null)
        //     {
        //         return 0;
        //     }
        //     return Math.Max(MaxDepth(root.left), MaxDepth(root.right)) + 1;
        // }

        //层序遍历 用以前的队列存储的方法
        public int MaxDepth(TreeNode root)
        {
            List<TreeNode> que_Node = new List<TreeNode>();
            List<TreeNode> list = new List<TreeNode>();
            if (root == null)
            {
                return 0;
            }
            int deep = 1;
            que_Node.Add(root);

            while (que_Node.Count > 0)
            {
                for (int i = 0; i < que_Node.Count; i++)
                {
                    if (que_Node[i].left != null)
                    {
                        que_Node.Add(que_Node[i].left);
                    }
                    if (que_Node[i].right != null)
                    {
                        que_Node.Add(que_Node[i].right);
                    }
                }
                que_Node = list;
                deep++;
            }
            return deep;
        }


        //查找二叉搜索树的最近公告父节点
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
        {

            List<TreeNode> left_list = returnNode(root, p);
            List<TreeNode> right_list = returnNode(root, q);

            for (int i = 0; i < left_list.Count; i++)
            {
                if (left_list[i].val == right_list[i].val)
                {
                    return left_list[i];
                }
            }
            return root;

        }

        //二叉搜索树 ：左节点<=根节点<=右节点

        //将二叉搜索树的每个父节点放入数组进行存储，
        public List<TreeNode> returnNode(TreeNode root, TreeNode taget)
        {
            List<TreeNode> list = new List<TreeNode>();

            while (root.val != taget.val)
            {
                if (root.val < taget.val)
                {
                    list.Add(root);
                    root = root.right;

                }
                else
                {
                    list.Add(root);
                    root = root.left;
                }
            }
            list.Add(root);
            return list;
        }
        public int[] SingleNumbers(int[] nums)
        {
            Dictionary<int, int> dic = new Dictionary<int, int>();
            for (int i = 0; i < nums.Length; i++)
            {
                if (dic.ContainsKey(nums[i]) == false) //没有这个值的时候
                {
                    dic.Add(nums[i], 1);
                }
                else
                {
                    dic[nums[i]]++;
                }
            }
            int[] result = new int[2];
            int count = 0;
            foreach (var item in dic)
            {
                if (item.Value == 1)
                {

                    result[count] = item.Key;
                    count++;
                }
            }

            return result;
        }

    }

}



